The present invention relates to the field of communication networks, and, more particularly, to mobile ad-hoc wireless networks and related methods.
Wireless networks have experienced increased development in the past decade. One of the most rapidly developing areas is mobile ad-hoc networks. Physically, a mobile ad-hoc network includes a number of geographically-distributed, potentially mobile nodes sharing a common radio channel. Compared with other types of networks, such as cellular networks or satellite networks, the most distinctive feature of mobile ad-hoc networks is the lack of any fixed infrastructure. The network may be formed of mobile nodes only, and a network is created xe2x80x9con the flyxe2x80x9d as the nodes transmit with each other. The network does not depend on a particular node and dynamically adjusts as some nodes join or others leave the network.
Because of these unique characteristics, routing protocols for governing data flow within ad-hoc networks are required which can adapt to frequent topology changes. Two basic categories of ad-hoc routing protocols have emerged in recent years, namely reactive or xe2x80x9con-demandxe2x80x9d protocols, and proactive or table-driven protocols. Reactive protocols collect routing information when a particular route is required to a destination in response to a route request. Examples of reactive protocols include ad-hoc on demand distance vector (AODV) routing, dynamic source routing (DSR), and the temporally ordered routing algorithm (TORA).
On the other hand, proactive routing protocols attempt to maintain consistent, up-to-date routing information from each node to every other node in the network. Such protocols typically require each node to maintain one or more tables to store routing information, and they respond to changes in network topology by propagating updates throughout the network to maintain a consistent view of the network. Examples of such proactive routing protocols include destination-sequenced distance-vector (DSDV) routing, which is disclosed in U.S. Pat. No. 5,412,654 to Perkins; the wireless routing protocol (WRP); and clusterhead gateway switch routing (CGSR). A hybrid protocol which uses both proactive and reactive approaches is the zone routing protocol (ZRP), which is disclosed in U.S. Pat. No. 6,304,556 to Haas.
One challenge to the advancement of ad-hoc network development is that of extending such networks to encompass large numbers of nodes. One prior art attempt to do so utilizes xe2x80x9cspinexe2x80x9d routing, such as in the optimal spine routing (OSR) approach disclosed by Das et al. in xe2x80x9cRouting in Ad-Hoc Networks using Minimum Connected Dominating Sets,xe2x80x9d IEEE Int. Conf. On Commun. (ICC ""97), 1997. In this approach, a spine or xe2x80x9cvirtual backbonexe2x80x9d is defined such that each network node is no more than one hop from a spine node. Global topology (link state) is maintained at each spine node, and a link-state routing algorithm is run at each spine node to produce current routes to every destination.
Another related approach is clustered spine routing (CSR), which is disclosed by Das et al. in xe2x80x9cRouting in Ad-Hoc Networks using a Spine,xe2x80x9d IEEE Int. Conf. On Computer Commun. and Networks (IC3N ""97), 1997. this approach is intended to extend the applicability of spine routing to larger network sizes by grouping the nodes in clusters and adding a second hierarchical level to the OSR approach. Yet another approach is known as partial knowledge spine routing (PSR) which is disclosed by Sivakumar et al. in xe2x80x9cThe Clade Vertebrata: Spines and Routing in Ad-Hoc Networks,xe2x80x9d IEEE Symposium On Computer and Commun., 1998.
One common characteristic of each of the above prior art cluster/spine approaches is that they each rely on proactive routing. One potential drawback of proactive routing is that it typically requires a significant amount of routing overhead to maintain optimal routes to all destinations at all times. This problem may become particularly acute when applied to ad-hoc networks including a very large number of nodes.
In view of the foregoing background, it is therefore an object of the present invention to provide a method for sending data in ad-hoc networks that is particularly well suited for networks having a relatively large number of nodes and which provides route error recovery.
This and other objects, features, and advantages in accordance with the present invention are provided by a method for sending data in a mobile ad-hoc network including a plurality of nodes grouped into clusters of nodes and a plurality of wireless links connecting the plurality of nodes, where each cluster has a designated cluster leader node. The method may include sending a cluster-level route request from a source node of a source cluster to a cluster leader node of the source cluster, and determining a cluster-level route through the source cluster and a destination cluster including a destination node responsive to the cluster-level route request and using a plurality of the cluster leader nodes. Furthermore, the method may also include determining node-level routes through each cluster along the cluster-level route to a cluster target node in a next cluster along the cluster-level route, and transferring the data from the source node to the destination node using the node-level routes.
Moreover, if a node-level route failure occurs along a node-level route, a new node-level route may advantageously be determined therefor. Similarly, if a cluster-level route failure occurs between adjacent clusters along the cluster-level route, a cluster-level route error message may be sent to the source node, and new cluster-level and node-level routes determined responsive thereto, at which the data may be transferred using the new node-level routes. More particularly, the node-level routes may be determined using the dynamic source routing (DSR) protocol or the ad-hoc on-demand vector routing (AODV) protocol, for example.
Additionally, the method may also include sending the cluster-level route error message from a cluster target node immediately upstream from where the cluster-level failure occurred to its respective cluster leader node. Further, the cluster-level route error message may then be sent to each cluster leader node upstream therefrom. Determining the cluster-level route may also include storing, at each cluster leader node except the destination cluster leader node, an address of a next cluster leader node along the cluster route. This will be the case when AODV is used as the base routing protocol, for example. The method may therefore also advantageously include deleting the next cluster leader node address from each cluster leader node upstream from where the cluster-level failure occurred. That is, the location of each xe2x80x9chopxe2x80x9d along the cluster-level route is deleted from each cluster leader node since the cluster-level route is no longer valid.
Determining the cluster-level route may include determining designated communication links between the cluster leader nodes, and sending a cluster leader node route request from the cluster leader node of the source cluster to the remaining cluster leaders via the designated communication links. Further, a cluster leader node route reply may be returned from the cluster leader node of the destination cluster to the cluster leader node of the source cluster along a delivery route of the cluster leader node route request.
More specifically, at least one of the designated communications links may include a node that is not a cluster leader node. Further, each cluster leader node may store addresses of adjacent cluster leader nodes, and sending the cluster leader node route request may include sending the cluster leader node route request from each cluster leader node to its adjacent cluster leader nodes. The adjacent cluster leader nodes may also be periodically polled to maintain current addresses therefor. Also, the delivery route may have a least number of cluster leader nodes between the cluster leader nodes of the source and destination clusters, and at least one of the node-level routes need not include a cluster leader node. Other path metrics such as delay, link capacities, availability, etc., may also be useful in determining the best route.
A mobile ad-hoc network is also provided according to the present invention and may include a plurality of nodes grouped into clusters of nodes, each cluster having a designated cluster leader node, and a plurality of wireless links connecting said plurality of nodes. The plurality of nodes may send data therebetween and perform route error recovery as briefly outlined above.